#ifndef LEETCODE_CN_CPP_PROBLEMS_76_H
#define LEETCODE_CN_CPP_PROBLEMS_76_H

#include <array>
#include <climits>
#include <string>

using namespace std;

namespace problem_76
{

class Solution
{
private:
    constexpr bool ok(const array<int, 128> &sCounts, const array<int, 128> &tCounts)
    {
        for (int i = 0; i < 128; ++i)
            if (sCounts[i] < tCounts[i])
                return false;
        return true;
    }

public:
    string minWindow(string s, string t)
    {
        if (s.empty() || t.empty())
            return {};
        array<int, 128> sCounts{0}, tCounts{0};
        for (auto c : t)
            tCounts[c] += 1;
        int left = 0, right = 0;
        int minWindowLeft = -1, minWindowSize = INT_MAX, len;
        sCounts[s[0]] = 1;
        while (left < s.size() && right < s.size() && left <= right)
        {
            if (!ok(sCounts, tCounts))
            {
                sCounts[s[++right]] += 1;
                continue;
            }
            len = right - left + 1;
            if (len < minWindowSize)
            {
                minWindowLeft = left;
                minWindowSize = len;
            }
            sCounts[s[left++]] -= 1;
        }
        if (minWindowLeft == -1)
            return {};
        return s.substr(minWindowLeft, minWindowSize);
    }
};

}; // namespace problem_76

#endif //LEETCODE_CN_CPP_PROBLEMS_76_H
